CS152 Fall 2008Practice Midterm 1

To study for the midterm I would suggest you: (1) Know how to do (by heart) all the practice problems. (2) Go over your notes at least three times. Second and third time try to see how much you can remember from the first time. (3) Go over the homework problems. (4) Try to create your own problems similar to the ones I have given and solve them. (5) Skim the relevant sections from the book. (6) If you want to study in groups, at this point you are ready to quiz each other. The practice midterm is below. Here are some facts about the actual midterm: (a) It is closed book, closed notes. Nothing will be permitted on your desk except your pen (pencil) and test. (b) You should bring photo ID. (c) There will be more than one version of the test. Each version will be of comparable difficulty. (d) One problem (less typos) on the actual test will be from the practice test. (e) One problem on the actual test will be about one of my HW solutions.

1. What does it mean for a programming language to be Turing complete? What does it mean for a language to be humanly readable? Machine readable?

2. Give an example of a data abstraction and of a control abstraction.

3. In what language did formatted output first appear? In what language did object-orientation first appear?

4. Give a regular expression for C style comments. Draw a finite automata which recognizes C style comments.

5. Consider the grammar <A> ::= <B>| <C> ; <B>::= a|b ; <C> ::= <A> a <A>. Is the string aaa in the language? If so give a parse tree. Is this language ambiguous? Prove your answer.

6. Draw the syntax diagram for the grammar of (5).

7. What is left factoring a grammar? In addition to your explanation give an example of a grammar rule which you left factor.

8. Give an example program where static and dynamic scoping of variables would yield the same output and an example where they would yield different output.

9. Define and give a box and circle diagram illustrating: assignment by sharing; assignment by cloning

10. Briefly describe what ADT-style Object Orientation is and give some example languages. Then do the same for message passing style object-orientation.